/*
 * @lc app=leetcode.cn id=440 lang=cpp
 *
 * [440] 字典序的第K小数字
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>

using namespace std;
// @lc code=start
class Solution {
public:
    int findKthNumber(int n, int k) {
        //根节点
        int root = 1;
        int cur = root; // 第 k 小的数一定正在 以 (和cur同一层的一个节点) 为根的树中
        k --;
        
        while (k > 0) {
            long long left = cur;
            long long right = cur + 1;
            //每个节点的子节点数
            int node_num = 0;
            
            // 统计树 以 cur 为根的数中小于 n 的节点个数
            while (left <= n) {
                node_num += min(right, (long long)(n + 1)) - left;
                left *= 10;
                right *= 10;
            }
            
            // 如果小于 k, 则表明第 k 小的数, 不在以 cur 为根的数中, 需要查询下一个树(以 cur + 1 为根)
            // 同时, 由于以 cur 为根的树有 node_num 个节点, 因此需要更新 k
            if (node_num <= k) {
                k -= node_num;
                cur ++;
            }
            // 如果大于 k, 表明第 k 小的数, 在以 cur 为根的数中(也就是当前位被确定, 进入下一位查询)
            // 因此, 可以进入以cur为根的树的下一层进行查询, 同样地需要更新 k (减去根节点)
            else {
                k --;
                cur *= 10;
            }
        }
        return cur;  
    }
};
// @lc code=end

